package com.lxq.LeetCode.strStr;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        System.out.println(strStr("abcdef", "ddd"));
    }

    //KMP
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        System.out.println(Arrays.toString(pi));
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
//    public static int strStr(String haystack, String needle) {
//        if ("".equals(needle)) {
//            return 0;
//        }
//        if (needle.length() > haystack.length()) {
//            return -1;
//        }
//        int res = -1;
//        for (int i = 0; i < haystack.length(); i++) {
//            //自己写
//            if (haystack.charAt(i) == needle.charAt(0)) {
//                int pi = i, j = 0;
//                while (pi < haystack.length() &&j < needle.length() &&haystack.charAt(pi) == needle.charAt(j)) {
//                    pi++;
//                    j++;
//                }
//                if (j == needle.length()){
//                    return i;
//                }
//            }
//            //用轮子
////            if (haystack.charAt(i) == needle.charAt(0) && haystack.startsWith(needle, i)) {
////                return i;
////            }
//        }
//        return res;
//    }
}
